package com.atwy.graph.directedgraph;

/**
 * @Author: 小王子火
 * @Date: 2022/3/18
 * 拓扑排序：给定一幅有向图，将所有的顶点排序，使得所有的
 * 有向边均从排在前面的元素指向排在后面的元素。
 *
 * 优先级限制下的调度问题。给定一组需要完成的任务，以及一组关于任务完成的先后次序的优
 * 先级限制。在满足限制条件的前提下应该如何安排并完成所有任务？
 *
 * 拓扑排序一定是有向无环图（DAG）
 *
 * 一幅有向无环图的拓扑顺序即为所有顶点的逆后序排列
 * 对于任意边v->w，在调用dfs(v)时，
 * 一定是dfs(w)在dfs(v)之前完成，因此在后序排列中，w排在v的前面而在逆后序中w排在v的后面，
 * 因此任意一条边v->w都如我们所愿地从排名较前顶点指向排名较后的顶点。
 *
 * 二叉树的后序遍历是什么时候？遍历完左右子树之后才会执行后序遍历位置的代码。
 * 换句话说，当左右子树的节点都被装到结果列表里面了，根节点才会被装进去。
 *
 * 后序遍历的这一特点很重要，
 * 之所以拓扑排序的基础是后序遍历， 是因为一个任务必须在等到所有的依赖任务都完成之后才能开始开始执行。
 * 你把每个任务理解成二叉树里面的节点，这个任务所依赖的任务理解成子节点，
 * 那你是不是应该先把所有子节点处理完再处理父节点？这是不是就是后序遍历？
 *
 * 为什么还要把后序遍历结果反转，才是最终的拓扑排序结果。
 *
 * 我们说一个节点可以理解为一个任务，这个节点的子节点理解为这个任务的依赖，
 * 但你注意我们之前说的依赖关系的表示：如果做完A才能去做B，那么就有一条从A指向B的有向边，表示B依赖A。
 *
 * 总之，你记住拓扑排序就是后序遍历反转之后的结果，且拓扑排序只能针对有向无环图，进行拓扑排序之前要进行环检测.
 *  https://mp.weixin.qq.com/s/7nP92FhCTpTKIAplj_xWpA
 * */
public class Topological {
    /**
     * 顶点的拓扑排序
     */
    private Iterable<Integer> order;

    public Topological(IDigraph graph) {
        // 首先对图进行检查，判断是否有环
        DirectedCycle cycleFind = new DirectedCycle(graph);
        if(!cycleFind.hasCycle()){
            // DAG才可以进行拓扑排序
            DepthFirstOrder dfsOrder = new DepthFirstOrder(graph);
            // 顶点逆后序排列
            order = dfsOrder.reversePost();

        }
    }

    public Iterable<Integer> order(){
        return order;
    }

    public boolean isDAG(){
        return order != null;
    }
}
